#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <SeqQueue.h>
#include "graph.h"

//根据字符获得下标
static int get_xb(mgraph *g,char v)
{
		int i;
		for(i = 0;i < g->vexnum;i++)
				if(g->V[i] == v)
						return i;
		return -1;
}

mgraph *graph_create()
{
		mgraph *g = malloc(sizeof(mgraph));
		g->vexnum = 0;
		g->arcnum = 0;

		printf("请输入顶点数组\n");	
		scanf("%s%*c",g->V);

		g->vexnum = strlen(g->V);
//初始化权值
		for(int i = 0;i < g->vexnum;i++)
		{
				for(int j = 0;j < g->vexnum;j++)
				{
						g->A[i][j] = VERY_BIG;
				}
		}
		printf("请输入权关系\n");
		while(1)
		{
				char s,p;
				int i,j,w;
				scanf("%c%c%d%*c",&s,&p,&w);

				if(s == '#')
						break;
//获取矩阵下标
				i = get_xb(g,s);
				j = get_xb(g,p);

				if(i == -1 || j == -1)
				{
						continue;
				}
//赋权值				
				g->A[i][j] = w;
				g->arcnum++;
		}
		return g;
}
//打印图
void graph_display(mgraph *g)
{
		int i,j;

		for(i = 0;i < g->vexnum;i++)
		{
				printf("%c\t",g->V[i]);
		}
		printf("\n");
		for(i = 0;i < g->vexnum;i++)
		{
				for(j = 0;j < g->vexnum;j++)
				{
						printf("%d\t",g->A[i][j]);
				}
				printf("\n");
		}
}

//获取存在的顶点关系
static int get_next_first(mgraph *g,int v0,int v)
{
		int i;
		for(i = v;i < g->vexnum;i++)
		{
				if(g->A[v0][i] != VERY_BIG)
						return i;
		}
		return -1;
}

//设置辅助访问变量
//visited[0]:未访问
//visited[1]:已访问
int visited[Max];	
static void graph_DFS(mgraph *g,int v0)
{
		printf("%c ",g->V[v0]);
		visited[v0] = 1;

		int k;
		//从第一个坐标开始
		for(k = get_next_first(g,v0,0);k != -1;k = get_next_first(g,v0,k+1))
		{
				if(visited[k] != 1)
					graph_DFS(g,k);
		}
}

//遍历图中所有点，包括非连同图
void DFSTRAVER(mgraph *g)
{
		int i;
		for(i = 0;i < g->vexnum;i++)
				visited[i] = 0;
		for(i = 0;i < g->vexnum;i++)
		{
				if(visited[i] != 1)
						graph_DFS(g,i);
		}
}

static void graph_BFS(mgraph *g,int v0)
{
		queue_head *que = NULL;
		que = Init_Queue();
//入队第一个元素
		EnQueue(que,g->V[v0]);
		visited[v0] = 1;
//队列不为空时循环出队，每出队一个元素，将这个元素的所有有效边入队
		while(!IsEmpty_Queue(que))
		{
				Datatype receive;
				DeQueue(que,&receive);
				printf("%c ",receive);

				int k;
				for(k = get_next_first(g,v0,0);k != -1;k = get_next_first(g,v0,k+1))
				{
						if(visited[k] != 1)
						{
								EnQueue(que,g->V[k]);
								visited[k] = 1;
						}
				}
		}

		Destroy_Queue(&que);
}
//广度优先遍历所有点
void BFSTRAVER(mgraph *g)
{
		int i;
		for(i = 0;i < g->vexnum;i++)
				visited[i] = 0;
		for(i = 0;i < g->vexnum;i++)
		{
				if(visited[i] != 1)
						graph_BFS(g,i);
		}

}
/*功能：迪杰斯特拉法
 *@s[Max]:s[0]:未找到最短路径
 		  s[1]:已找到最短路径
 *@dist[Max]:
 		  dist[i]:表示从源点v到vi的最短路径的距离
 *@path[Max][Max]:
 *		  path[i]:表示从源点v到vi所经过的所有点
 *
 */

int s[Max];
int dist[Max];
char path[Max][Max];

void Dijkstra(mgraph *g,int v0)
{
		int i,j;
		for(i = 0;i < g->vexnum;i++)
		{
				s[i] = 0;
				dist[i] = g->A[v0][i];
				//初始化
				memset(path[i],'\0',Max);
				//源点
				path[i][0] = g->V[v0];
				//目标点
				path[i][1] = g->V[i];
		}
		s[v0] = 1;

		int n = 0;
		//循环n-1次
		while(++n < g->vexnum)
		{	
				int min_vaule = VERY_BIG;
				int u;
		//找到最短路径的下标u，并将s[u]置为1		
				for(i = 0;i < g->vexnum;i++)
				{
						if(s[i] == 0)
						{
								if(dist[i] < min_vaule)
								{
										min_vaule = dist[i];
										u = i;
								}
						}
				}
				s[u] = 1;

				for(i = 0;i < g->vexnum;i++)
				{
						if(s[i] == 0)
						{
		//当间接路径小于当前最小直接路径时，更新最小路径dist[i]和path[i]					
								if(dist[u] + g->A[u][i] < dist[i])
								{
										dist[i] = dist[u] + g->A[u][i];
										strcpy(path[i],path[u]);
										//最后要到的目标点
										path[i][strlen(path[i])] = g->V[i];
								}
						}
				}
		}
//打印
		for(i = 0;i < g->vexnum;i++)
		{
				if(i == v0)
				{
						continue;
				}
				printf("%c->%c [%d] ",g->V[v0],g->V[i],dist[i]);
				for(j = 0;j < strlen(path[i])-1;j++)
				{
						printf("%c->",path[i][j]);
				}
				printf("%c\n",path[i][j]);
		}
}
